package com.LeeCode;

import java.util.HashMap;
import java.util.Map;

/**
 * 最小覆盖子串
 */

public class Code076 {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(new Code076().minWindow(s, t));
    }

    public String minWindow(String s, String t) {

        Map<Character, Integer> Smap = new HashMap<>();
        Map<Character, Integer> Tmap = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            Tmap.put(t.charAt(i), Tmap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        while (right < s.length()) {
            right++;
            if (right < s.length() && Tmap.containsKey(s.charAt(right))) {
                Smap.put(s.charAt(right), Smap.getOrDefault(s.charAt(right), 0) + 1);
            }
            while (check(Smap, Tmap) && left <= right) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    ansL = left;
                    ansR = ansL + len;
                }
                if (Tmap.containsKey(s.charAt(left))) {
                    Smap.put(s.charAt(left), Smap.get(s.charAt(left)) - 1);
                }
                left++;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check(Map<Character, Integer> Smap, Map<Character, Integer> Tmap) {
        for (Character key : Tmap.keySet()) {
            if (Tmap.get(key) > Smap.getOrDefault(key, 0)) {
                return false;
            }
        }
        return true;
    }
}
